package sort.quick;

import util.Util;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 1, 0, 3, 4, 2, 6, 7, 8, 5};
        // int[] arr = Util.generateArray(10);

        Util.print(arr);
        quickSort(arr);
        Util.print(arr);

    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int midIndex = partition(arr, start, end);
            quickSort(arr, start, midIndex - 1);
            quickSort(arr, midIndex + 1, end);
        }
    }

    /**
     * 固定切分
     */
    private static int partition(int[] arr, int start, int end) {
        int left = start;
        int right = end;
        int temp = arr[left];

        while (left < right) {
            // 从后半部分向前扫描
            while (left < right && temp <= arr[right]) {
                --right;
            }
            arr[left] = arr[right];

            // 从前半部分向后扫描
            while (left < right && temp >= arr[left]) {
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }

    /**
     * 三数取中切分
     */
    private static int partition1(int[] arr, int start, int end) {

        int mid = (end - start) / 2 + start;

        if (arr[mid] > arr[end]) {
            int temp = arr[mid];
            arr[mid] = arr[end];
            arr[end] = temp;
        }

        if (arr[start] > arr[end]) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }

        if (arr[mid] > arr[start]) {
            int temp = arr[mid];
            arr[mid] = arr[start];
            arr[start] = temp;
        }

        int key = arr[start];

        while (start < end) {
            while (arr[end] >= key && end > start) {
                end--;
            }
            arr[start] = arr[end];
            while (arr[start] <= key && end > start) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[end] = key;
        return end;

    }

}
